<!DOCTYPE html>
<html lang="zh-CN">
<!--浏览器搞笑标题-->
<script type="text/javascript" src="/js/FunnyTitle.js"></script>






<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/binblog/img/binblog.ico">
  <link rel="icon" type="image/png" href="/binblog/img/binblog.ico">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="leo-bin">
  <meta name="keywords" content="">
  <title>常用算法之排序算法和查找算法 - 阿斌的个人博客</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/binblog/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/dracula.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/binblog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


<meta name="generator" content="Hexo 4.2.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/binblog/">&nbsp;<strong>Abin的Blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/binblog/img/6.webp') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2020-07-16 19:53">
      2020年7月16日 晚上
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      4.3k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      52
       分钟
    </span>
  

  
  
    
      <!-- LeanCloud 统计文章PV -->
      <span id="leancloud-post-views-container" class="post-meta" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="leancloud-post-views"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
              <p class="note note-info">
                
                  本文最后更新于：2020年9月17日 晚上
                
              </p>
            
            <article class="markdown-body">
              <h1 id="常用算法之排序算法和查找算法"><a href="#常用算法之排序算法和查找算法" class="headerlink" title="常用算法之排序算法和查找算法"></a>常用算法之排序算法和查找算法</h1><h2 id="前话"><a href="#前话" class="headerlink" title="前话"></a>前话</h2><p>ok，今天我们还是照常说一点废话，呸！前话！</p>
<p>有的时候自己能够做到的事情就一定要拼尽全力的去争取，谁也不知道会发生什么。</p>
<p>一直以来我都坚信一句话：<strong><code>努力可能不会成功，但是不努力，一定不会成功！</code></strong></p>
<p><strong>今晚的鸡汤干了！</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/1.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<h2 id="查找算法"><a href="#查找算法" class="headerlink" title="查找算法"></a>查找算法</h2><h3 id="1）暴力查找"><a href="#1）暴力查找" class="headerlink" title="1）暴力查找"></a>1）暴力查找</h3><p>暴力查找，有多暴力呢？</p>
<p>只要你会敲代码，你写的第一个查找算法一定是这样子的！</p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">searchNumber</span><span class="hljs-params">(<span class="hljs-keyword">int</span> []nums,<span class="hljs-keyword">int</span> target)</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;nums.length;i++)&#123;
        <span class="hljs-comment">//找到返回下标</span>
        <span class="hljs-keyword">if</span>(nums[i]==target)&#123;
            <span class="hljs-keyword">return</span> i;
        &#125;
    &#125;
    <span class="hljs-comment">//没找到</span>
    <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
&#125;</code></pre></div>
<p><strong><code>时间复杂度：O(n)</code></strong></p>
<p><strong><code>空间复杂度：O(1)</code></strong></p>
<p><br/></p>
<p>其实这个算法没什么毛病，简单，易懂，稳定。</p>
<p>而且不管什么情况下都能够在稳定的时间复杂度O(n)内找出来。</p>
<p>但是，这个算法，在程序员眼里，可能，那个，比较，low（小声bb）。</p>
<p>okok，anyway，所以身边一说起查找算法，都会尽量避免写上面这个，而是会写下面这个👇</p>
<p><br/></p>
<h3 id="2）二分查找"><a href="#2）二分查找" class="headerlink" title="2）二分查找"></a>2）二分查找</h3><p>二分查找，顾名思义，就是一半一半的找，听起来好像蛮快的。</p>
<p><strong>核心思想：</strong></p>
<p>二分查找，就是从有序数组的中间开始找。</p>
<p>先设立三个指针，left，mid，right，分别指向数组的最前，中间，最后的位置。</p>
<p>每次都让中间元素和目标元素比对。</p>
<p>如果目标元素比中间元素要大的话。</p>
<p>根据排序的特点，很显然，目标元素就一定在中间元素的右边。</p>
<p>要小的话，那就在左边。</p>
<p>就这样根据和目标元素进行比较，从而一步一步的缩小正确范围。</p>
<p>每次都少一半，整体的比较次数，就是<strong>log2(n)</strong>！</p>
<p><br/></p>
<p><strong>看代码：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearch</span><span class="hljs-params">(<span class="hljs-keyword">int</span> []nums,<span class="hljs-keyword">int</span> target)</span></span>&#123;
    <span class="hljs-keyword">int</span> left=<span class="hljs-number">0</span>,right=nums.length-<span class="hljs-number">1</span>;
    <span class="hljs-keyword">while</span>(left&lt;=right)&#123;
        <span class="hljs-comment">//做减法而不是加法，防止int溢出</span>
        <span class="hljs-keyword">int</span> mid=left+(right-left)/<span class="hljs-number">2</span>;
        <span class="hljs-keyword">if</span>(target==nums[mid])&#123;
            <span class="hljs-keyword">return</span> mid;
        &#125;<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(target&gt;nums[i])&#123;
            left=mid+<span class="hljs-number">1</span>;
        &#125;<span class="hljs-keyword">else</span>&#123;
            right=mid-<span class="hljs-number">1</span>;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
&#125;</code></pre></div>
<p><br></p>
<p><strong>其实递归也可以做，思想差不多，类似于分治找区间</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearch</span><span class="hljs-params">(<span class="hljs-keyword">int</span> []nums,<span class="hljs-keyword">int</span> target,<span class="hljs-keyword">int</span> left,<span class="hljs-keyword">int</span> right)</span></span>&#123;
    <span class="hljs-keyword">int</span> mid=left+(right-left)/<span class="hljs-number">2</span>;
    <span class="hljs-comment">//递归结束条件</span>
    <span class="hljs-keyword">if</span>(mid&lt;<span class="hljs-number">0</span>||mid&gt;nums.length||left&gt;right)&#123;
        <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
    &#125;
    <span class="hljs-comment">//满足条件就直接返回咯</span>
    <span class="hljs-keyword">if</span>(nums[mid]==target)&#123;
        <span class="hljs-keyword">return</span> mid;
    &#125;
    <span class="hljs-comment">//根据大小进行分治</span>
    <span class="hljs-keyword">if</span>(nums[mid]&gt;target)&#123;
        <span class="hljs-keyword">return</span> binarySearch(nums,target,left,mid-<span class="hljs-number">1</span>;)
    &#125;<span class="hljs-keyword">else</span>&#123;
        <span class="hljs-keyword">return</span> binarySearch(nums,target,mid+<span class="hljs-number">1</span>,right);
    &#125;
&#125;</code></pre></div>
<p><br></p>
<p><strong>二分真的很快吗？事实也确实是这样子的，每次都可以去掉一半的选择，整体的时间复杂度蹭蹭蹭的往上涨！</strong></p>
<p><strong>但是呢，二分查找的前提，一定是目标数组是有序的！</strong></p>
<p><strong>怎么说呢，如果是无序的查找，你叫天王老子来也是用的上面那个暴力算法👆</strong></p>
<p><strong>但是有序，就可以利用一些技巧来大幅减少查找次数。</strong></p>
<p><br/></p>
<p><strong><code>时间复杂度：O(log(n))</code></strong></p>
<p><strong><code>空间复杂度：O(1)</code></strong></p>
<p><br/></p>
<h2 id="排序算法"><a href="#排序算法" class="headerlink" title="排序算法"></a>排序算法</h2><p>在讲排序算法之前要先介绍下一些<strong>专业术语</strong>：</p>
<ul>
<li><strong>稳定</strong>：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。</li>
<li><strong>不稳定</strong>：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。</li>
<li><strong>内排序</strong>：所有排序操作都在<code>内存</code>中完成。</li>
<li><strong>外排序</strong>：由于数据太大，因此把数据放在<code>磁盘</code>中，而排序通过磁盘和内存的数据传输才能进行。</li>
</ul>
<p><br/></p>
<p>这么多名词，还有时间复杂度要记，<strong>come on，give me a break~</strong></p>
<p><strong>没事，这里给出一个总结表，忘记了就多看看呗！</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/所有排序算法特点统计表.jpg" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><strong>限于本人时间精力有限，十大排序算法我这里只给出了6种最常见的算法总结。</strong></p>
<p><strong>所有动图都是取自参考文章，如有侵权请联系我删除!</strong></p>
<p><br/></p>
<p><strong><code>排序所用测试用例</code>：</strong></p>
<div class="hljs"><pre><code class="hljs java">&#123;<span class="hljs-number">3</span>, <span class="hljs-number">2</span>, <span class="hljs-number">5</span>, <span class="hljs-number">4</span>, <span class="hljs-number">1</span>&#125;</code></pre></div>
<p><br/></p>
<h3 id="1）冒泡排序"><a href="#1）冒泡排序" class="headerlink" title="1）冒泡排序"></a>1）冒泡排序</h3><p>冒泡，看名字就知道。</p>
<p>元素在排序的过程就像水泡一样从下往上走，越走越大，直到找到一个合适的地方。</p>
<p>在这里，因为每次都从第一个元素开始，每次都比较相邻的两个元素的大小，直到最后。</p>
<p>所以，第一次遍历的过程中，数组中的最大值，就会像气泡一样从某个位置浮到最后的位置去。</p>
<p><strong>代码可参考：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">bubbleSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums)</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;nums.length;i++)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;nums.length-<span class="hljs-number">1</span>-i;j++)&#123;
            <span class="hljs-comment">//交换</span>
            <span class="hljs-keyword">if</span>(nums[j]&gt;nums[j+<span class="hljs-number">1</span>])&#123;
                <span class="hljs-keyword">int</span> t=nums[j];
                nums[j]=nums[j+<span class="hljs-number">1</span>];
                nums[j+<span class="hljs-number">1</span>]=t;
            &#125;
        &#125;
    &#125;
&#125;</code></pre></div>
<p><br/></p>
<p><br/></p>
<p><strong><code>执行流程动图：</code></strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/冒泡排序.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><br/></p>
<p><strong><code>时间复杂度：O(n*n)(平均)</code></strong></p>
<p><strong><code>空间复杂度：O(1)</code></strong></p>
<p><br/></p>
<p><br/></p>
<p>这种写法肯定没问题，但是我们可以想一下，如果经过内部的一次遍历，或者两次，三次，此时的数组已经有序了怎么办？</p>
<p>按照这种写法，那肯定会不撞南墙不肯回头了亚！</p>
<p><br/></p>
<p><strong>所以我们可以优化一下，当数组已经有序的时候就退出循环，提高效率。</strong></p>
<p><br/></p>
<p>那退出的条件是什么呢？</p>
<p>我们可以想到，因为每次内部的循环体都会走一遍数组，遇到无序的元素就会进行交换。</p>
<p>但是如果走了一遍内部排序，但是一个元素<strong>都没有交换</strong>意味着什么？没错！此时就是退出循环的绝好时机！</p>
<p><br/></p>
<p><strong>修改之后的代码：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">bubbleSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums)</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;nums.length;i++)&#123;
        <span class="hljs-keyword">boolean</span> isSorted=<span class="hljs-keyword">true</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;nums.length-<span class="hljs-number">1</span>-i;j++)&#123;
            <span class="hljs-keyword">if</span>(nums[j]&gt;nums[j+<span class="hljs-number">1</span>])&#123;
                <span class="hljs-comment">//此时还是无序</span>
                isSorted=<span class="hljs-keyword">false</span>;
                <span class="hljs-keyword">int</span> t=nums[j];
                nums[j]=nums[j+<span class="hljs-number">1</span>];
                nums[j+<span class="hljs-number">1</span>]=t;
            &#125;
        &#125;
        <span class="hljs-comment">//一次都没有交换那就退出循环了，此时的数组已经有序了</span>
        <span class="hljs-keyword">if</span>(isSorted)&#123;
            <span class="hljs-keyword">break</span>;
        &#125;
    &#125;
&#125;</code></pre></div>
<p><br/></p>
<h3 id="2）选择排序"><a href="#2）选择排序" class="headerlink" title="2）选择排序"></a>2）选择排序</h3><p>这种排序方式算是大家初学编程时写的最多的一种算法吧？</p>
<p>反正我是觉得简单易懂，干脆利落，（无脑暴力）。。。</p>
<p>基本思想就是每次都固定一个位置，然后每次用其他元素这个固定位置的元素进行对比。</p>
<p>通过这样的遍历，每次都能够找到某一个位置的元素。</p>
<p><br/></p>
<p><strong>可行代码如下：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">selectSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums)</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;nums.length;i++)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=i+<span class="hljs-number">1</span>;j&lt;nums.length;j++)&#123;
            <span class="hljs-keyword">if</span>(nums[i]&gt;nums[j])&#123;
                <span class="hljs-keyword">int</span> t=nums[i];
                nums[i]=nums[j];
                nums[j]=t;
            &#125;
        &#125;
    &#125;
&#125;</code></pre></div>
<p><br/></p>
<p><strong>执行流程动图：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/选择排序.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><strong><code>时间复杂度：O(n*n)</code></strong></p>
<p><strong><code>空间复杂度：O(1)</code></strong></p>
<p><br/></p>
<h3 id="3）插入排序"><a href="#3）插入排序" class="headerlink" title="3）插入排序"></a>3）插入排序</h3><p>ok，之前的都是热身，接下来就要开始难一点的了。做好准备！</p>
<p>插入排序，顾名思义，每次都进行插入？what？为什么插入还可以进行排序？</p>
<p><strong>我们假设现在的无序数组是：</strong></p>
<div class="hljs"><pre><code class="hljs java">&#123;<span class="hljs-number">3</span>,<span class="hljs-number">2</span>,<span class="hljs-number">5</span>,<span class="hljs-number">4</span>,<span class="hljs-number">1</span>&#125;</code></pre></div>
<p><br/></p>
<p>如果把第一个数单独看成一个数组：{3}，那它肯定是有序的对吧？</p>
<p>ok，我们按照顺序在往这个数组中插入一个2，此时的数组是：{3，2}。</p>
<p>要想继续保证数组的有序，是不是就需要进行比较并交换的操作了？</p>
<p>ok，我们让2和3比较，交换之后的数组是：{2，3}。</p>
<p>继续，插入一个5，{2，3，5}，因为不知道插入的数和前面的数的大小，所以也需要进行比较并交换。</p>
<p>但是很明显这里不需要进行交换，本来就是有序的。现在的数组是：{2，3，5}。</p>
<p>继续，插入一个4，{2，3，5，4}，ok，比较并交换得出：{2，3，4，5}。</p>
<p>最后一个元素就是：{2，3，4，5，1}，得出：{1，2，3，4，5}。</p>
<p><br/></p>
<p><strong>可参考代码如下：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insertSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums)</span></span>&#123;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;nums.length;i++)&#123;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=i;j&gt;<span class="hljs-number">0</span>;j--)&#123;
            <span class="hljs-keyword">if</span>(nums[j]&lt;nums[j-<span class="hljs-number">1</span>])&#123;
                <span class="hljs-keyword">int</span> t=nums[j];
                nums[j]=nums[j-<span class="hljs-number">1</span>];
                nums[j-<span class="hljs-number">1</span>]=t;
            &#125;
        &#125;
    &#125;
&#125;</code></pre></div>
<p><br/></p>
<p><strong>执行流程动图：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/插入排序.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><br/></p>
<p><strong><code>时间复杂度：O(n*n)</code></strong></p>
<p><strong><code>空间复杂度：O(1)</code></strong></p>
<p><br/></p>
<h3 id="4）快速排序"><a href="#4）快速排序" class="headerlink" title="4）快速排序"></a>4）快速排序</h3><p><strong>快速排序，是利用不断分治，将原数组变成多个区间，这多个区间之间是相对有序的。</strong></p>
<p>为什么说是相对有序呢？因为只是满足左边区间所有元素都小于右边区间中的所有元素。</p>
<p>但是通过不断的分治，最后整体就会变成有序！</p>
<p><br/></p>
<p><strong>不断的分治，我们可以通过递归实现。</strong></p>
<p>那一趟排序是如何将原数组变成相对有序的两个部分呢？</p>
<p>这一点我们可以通过双指针来实现！</p>
<p>分别设置三个指针left，mid，right（mid是为了找中轴元素）</p>
<p>那如何在排序之前就确定这个中轴值呢？</p>
<p>有两种方法！</p>
<p><strong>第一种就是直接选第一个元素作为中轴。</strong></p>
<p><strong>第二种就是随机从区间中找一个元素作为中轴。</strong></p>
<p>第一种方法其实不是很推荐，但是为了便于简单，所以选择了第一种。</p>
<p>至于为什么之后介绍。</p>
<p><br/></p>
<p><strong>参考代码：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">//快排</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">quickSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums,<span class="hljs-keyword">int</span> left ,<span class="hljs-keyword">int</span> right)</span></span>&#123;
    <span class="hljs-comment">//递归结束条件</span>
    <span class="hljs-keyword">if</span>(left &gt;= right)&#123;
        <span class="hljs-keyword">return</span> ;
    &#125;
    <span class="hljs-keyword">int</span> mid=partition(nums,left,right);
    quickSort(nums,left,mid-<span class="hljs-number">1</span>);
    quickSort(nums,mid+<span class="hljs-number">1</span>, right);
&#125;

<span class="hljs-comment">//分治</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">partition</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums,<span class="hljs-keyword">int</span> left ,<span class="hljs-keyword">int</span> right)</span></span>&#123;
    <span class="hljs-keyword">int</span> midValue=nums[left];
    <span class="hljs-keyword">int</span> midIndex=left;
    <span class="hljs-keyword">while</span>(left!=right)&#123;
        <span class="hljs-keyword">while</span>(left&lt;right&amp;&amp;nums[right]&gt;midValue)&#123;
            right--;
        &#125;
        <span class="hljs-keyword">while</span>(left&lt;right&amp;&amp;nums[left]&lt;=midValue)&#123;
            left++;
        &#125;
        <span class="hljs-keyword">if</span>(left&lt;right)&#123;
            swap(nums,left,right);
        &#125;
    &#125;
    <span class="hljs-comment">//将中轴还原到所在的位置</span>
    nums[midIndex]=nums[left];
    nums[left]=midValue;
    <span class="hljs-keyword">return</span> left;
&#125;

<span class="hljs-comment">//交换</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">swap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums,<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>&#123;
    <span class="hljs-keyword">int</span> t=nums[i];
    nums[i]=nums[j];
    nums[j]=t;
&#125;</code></pre></div>
<p><br/></p>
<p><strong>执行流程动图：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/快速排序.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><br/></p>
<p><strong><code>时间复杂度：O(n*log(n))</code></strong></p>
<p><strong><code>空间复杂度：O(log(n))</code></strong></p>
<p><br/></p>
<p>至于为什么不推荐选取区间的第一个元素作为中轴。</p>
<p>这是因为快速排序的效率直接取决于中轴的选取！</p>
<p>我们来看下面这一个测试用例：</p>
<div class="hljs"><pre><code class="hljs java">&#123;<span class="hljs-number">5</span>，<span class="hljs-number">4</span>，<span class="hljs-number">3</span>，<span class="hljs-number">2</span>，<span class="hljs-number">1</span>&#125;</code></pre></div>
<p><br/></p>
<p>我们跟着上面的算法思路走一遍流程：</p>
<p>首先确定5为中轴，然后右指针从右往左边扫描，直到碰到第一个比中轴小的元素。</p>
<p>ok，第一个元素就满足了，所有此时的right指针指向了1。</p>
<p>现在走左边指针left的逻辑，找第一个比中轴要大的元素，5直接跳过，然后指向4，3，2。最后直接就指向了1，此时退出循环。</p>
<p>然后对中轴复位，现在的数组变成了：{1，4，3，2，5}；</p>
<p>然后返回中轴的位置：4</p>
<p>然后经过分治，分成了两个数组：{1，4，3，2}和{5}。</p>
<p>单个5不用管，直接返回了。</p>
<p>现在重新对左边的数组走排序的逻辑。</p>
<p>现在选取的中轴就是：1</p>
<p>但是很显然这个中轴比所有元素都要小，不需要交换位置，结果自然就是返回自己的位置作为中轴。</p>
<p>然后继续进行分治：{1}和{4，3，2}。</p>
<p>然后你会发现，这个就和最初的情况是一样的了，所以导致的结果就是每次分治都是在对一个元素进行分组。</p>
<p>时间复杂度退化到了：O(n)</p>
<p><strong>所以总体的时间复杂度：O(n*n)</strong></p>
<p><strong>空间复杂度也是一样：O(n)</strong></p>
<p><br/></p>
<p><strong>引起这个问题的原因就是因为每次选取的中轴都是一个极值！</strong></p>
<p><strong>要么是最大值，要么是最小值，所以就会导致每次都无法进行交换，起不到排序的作用。</strong></p>
<p><strong>所以解决方法就是每次在选取中轴的时候随机一点，尽量别抽到极值就行了。</strong></p>
<p><br/></p>
<h3 id="5）归并排序"><a href="#5）归并排序" class="headerlink" title="5）归并排序"></a>5）归并排序</h3><p><strong>归并排序很像快速排序，基本思路都是分而治之！</strong></p>
<p>不过归并排序是直接将原数组分成很多个小数组，然后让小数组内部实现有序。</p>
<p>然后合并这些小数组，再将合并之后的数组变得有序。</p>
<p>最后合并成的大数组就是一个有序的数组啦！</p>
<p><br/></p>
<p><strong>参考代码如下：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> [] mergeSort(<span class="hljs-keyword">int</span> [] nums)&#123;
    <span class="hljs-comment">//递归结束条件</span>
    <span class="hljs-keyword">if</span>(nums.length==<span class="hljs-number">1</span>)&#123;
        <span class="hljs-keyword">return</span> nums;
    &#125;
    <span class="hljs-keyword">int</span> mid=nums.length/<span class="hljs-number">2</span>;
    <span class="hljs-keyword">int</span> [] left=Arrays.copyOfRange(nums,<span class="hljs-number">0</span>,mid);
    <span class="hljs-keyword">int</span> [] right=Arrays.copyOfRange(nums,mid,nums.length);
    <span class="hljs-keyword">return</span> merge(mergeSort(left),mergeSort(right));
&#125;

<span class="hljs-comment">//归并并排序</span>
<span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> [] merge(<span class="hljs-keyword">int</span> [] left,<span class="hljs-keyword">int</span> []right)&#123;
    <span class="hljs-keyword">int</span> [] result=<span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[left.length+right.length];
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> index=<span class="hljs-number">0</span>,i=<span class="hljs-number">0</span>,j=<span class="hljs-number">0</span>;index&lt;result.length;index++)&#123;
        <span class="hljs-keyword">if</span>(i&gt;=left.length)&#123;
            result[index]=right[j++];
        &#125;<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(j&gt;=right.length)&#123;
            result[index]=left[i++];
        &#125;<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(left[i]&gt;right[j])&#123;
            result[index]=right[j++];
        &#125;<span class="hljs-keyword">else</span> &#123;
            result[index]=left[i++];
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> result;
&#125;</code></pre></div>
<p><br/></p>
<p><strong>执行流程动图：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/归并排序.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><strong>时间复杂度：O(n*log(n))</strong></p>
<p><strong>空间复杂度：O()</strong></p>
<p><br/></p>
<h3 id="6）堆排序"><a href="#6）堆排序" class="headerlink" title="6）堆排序"></a>6）堆排序</h3><p>堆排序和之前的排序不一样，这里是需要提前了解下<strong><code>二叉堆</code></strong>这个数据结构。</p>
<p>不仅仅是这里的堆排序，<strong>大顶堆</strong>，<strong>小顶堆</strong>，<strong>优先级队列</strong>都是基于<strong>二叉堆</strong>来实现的。</p>
<p><br/></p>
<p><strong>测试用例为：</strong></p>
<div class="hljs"><pre><code class="hljs java">&#123;<span class="hljs-number">2</span>, <span class="hljs-number">4</span>, <span class="hljs-number">1</span>, <span class="hljs-number">5</span>, <span class="hljs-number">7</span>, <span class="hljs-number">6</span>, <span class="hljs-number">8</span>, <span class="hljs-number">3</span>, <span class="hljs-number">9</span>&#125;</code></pre></div>
<p><br/></p>
<p>二叉堆和二叉树的区别就在于，二叉堆内部不是由节点构成的。</p>
<p>二叉堆直接通过数组的下标来表示。</p>
<p>比如说上面的测试用例可以表示成一颗普通的二叉树</p>
<p><strong>用树来表示就是：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/image-20200717001920706.png" srcset="/binblog/img/loading.gif" alt="image-20200717001920706"></p>
<p><br/></p>
<p><strong>注意：</strong></p>
<p>1.对于数组构成的二叉树，这棵树的最后一个非叶子节点位置：</p>
<script type="math/tex; mode=display">
nums.length-2/2</script><p>2.假设某个根节点的下标为parentIndex，那此根节点的左节点下标为：</p>
<script type="math/tex; mode=display">
2*parentIndex+1</script><p>3.右子节点的下标为：</p>
<script type="math/tex; mode=display">
2*parentIndex+2</script><p><br/></p>
<p><br/></p>
<p>但是这个并不表示任何一个二叉堆！</p>
<p>二叉堆分为两种类型：</p>
<p><strong>1.大顶堆。</strong></p>
<p><strong>2.小顶堆。</strong></p>
<p><br/></p>
<p><strong>特点：</strong></p>
<p>1.堆顶的元素要么是最大值，要么是最小值。</p>
<p>2.根节点一定要大于左右两个子节点或者小于左右两个子节点。</p>
<p><br/></p>
<p>所以我们要对原数组进行从小到大的排序，这里我们通过构造一棵<strong>大顶堆</strong>来实现（小顶堆也可以）。</p>
<p><br/></p>
<p><strong>那么如何构造一个大顶堆呢？</strong></p>
<p>我们可以通过下沉所有非叶子节点来实现！</p>
<p>每次从一个非叶子节点开始，比如说这里从最后一个非叶子节点：5，开始。</p>
<p>比较它的左右子树的大小，找到一个最大值替换掉当前的根节点。</p>
<p>直到当前的根节点无法下沉时，则退出下沉操作。</p>
<p>接下来开始下一个非叶子节点的下沉。</p>
<p>当所有非叶子节点都下沉完毕之后，此时的树就是一个大顶堆！堆顶元素就是元素的最大值。</p>
<p><br/></p>
<p><strong>构造完毕之后的大顶堆：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/image-20200717004122804.png" srcset="/binblog/img/loading.gif" alt="image-20200717004122804"></p>
<p><br/></p>
<p>可以看到，堆顶的元素就是最大值9</p>
<p>ok，大顶堆建完了，这个时候我们需要进行排序了！</p>
<p>其实排序的思路也很简单，就是每次都拿堆顶的元素和最后一个元素进行交换。</p>
<p>比如说现在的9和最后一个元素：4进行交换。</p>
<p>当4成为堆顶元素之后，继续做一次下沉操作，使得下一次取堆顶的元素时候保证堆顶元素是最大的！</p>
<p>这样一来，数组就变成有序的了！</p>
<p><br/></p>
<p><strong>参考代码：</strong></p>
<div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">//二叉堆的下沉操作</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">downAdjust</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums,<span class="hljs-keyword">int</span> parentIndex,<span class="hljs-keyword">int</span> len)</span></span>&#123;
    <span class="hljs-keyword">int</span> tmp=nums[parentIndex];
    <span class="hljs-keyword">int</span> childIndex=<span class="hljs-number">2</span>*parentIndex+<span class="hljs-number">1</span>;
    <span class="hljs-keyword">while</span>(childIndex&lt;len)&#123;
        <span class="hljs-comment">//确定要交换的子节点</span>
        <span class="hljs-keyword">if</span>(childIndex+<span class="hljs-number">1</span>&lt;len&amp;&amp;nums[childIndex+<span class="hljs-number">1</span>]&gt;nums[childIndex])&#123;
            childIndex++;
        &#125;
        <span class="hljs-keyword">if</span>(tmp&gt;nums[childIndex])&#123;
            <span class="hljs-keyword">return</span> ;
        &#125;
        <span class="hljs-comment">//修改子节点</span>
        nums[parentIndex]=nums[childIndex];
        parentIndex=childIndex;
        childIndex=<span class="hljs-number">2</span>*parentIndex+<span class="hljs-number">1</span>;
    &#125;
    <span class="hljs-comment">//交换当前的非叶子节点</span>
    nums[parentIndex]=tmp;
&#125;

<span class="hljs-comment">//堆排序</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">heapSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> [] nums)</span></span>&#123;
    <span class="hljs-comment">//1.先构建一颗大顶堆</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=(nums.length-<span class="hljs-number">2</span>)/<span class="hljs-number">2</span>;i&gt;=<span class="hljs-number">0</span>;i--)&#123;
        downAdjust(nums,i,nums.length);
    &#125;
    <span class="hljs-comment">//2.依次取当前堆顶的第一个值和数组的最后一个值进行交换</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=nums.length-<span class="hljs-number">1</span>;i&gt;=<span class="hljs-number">0</span>;i--)&#123;
        <span class="hljs-comment">//交换</span>
        <span class="hljs-keyword">int</span> t=nums[<span class="hljs-number">0</span>];
        nums[<span class="hljs-number">0</span>]=nums[i];
        nums[i]=t;
        <span class="hljs-comment">//继续下沉，保持大顶堆的特性</span>
        downAdjust(nums,<span class="hljs-number">0</span>,i);
    &#125;
&#125;</code></pre></div>
<p><br/></p>
<p><strong>执行流程动图：</strong></p>
<p><img src="https://bins-pic.oss-cn-shanghai.aliyuncs.com/mypic/堆排序.gif" srcset="/binblog/img/loading.gif" alt=""></p>
<p><br/></p>
<p><strong><code>时间复杂度：O(n*log(n))</code></strong></p>
<p><strong><code>空间复杂度：O(1)</code></strong></p>
<p><br/></p>
<h2 id="最后"><a href="#最后" class="headerlink" title="最后"></a>最后</h2><p><strong>ok，终于肝完了！！！！</strong></p>
<p><strong>现在是凌晨1点多，唉，身体越来越吃不消了，好困呀。</strong></p>
<p><strong>最后还是说一点，对于这些基本的，高频的算法，还是重头学一遍比较好。</strong></p>
<p><strong>毕竟这些传统的算法已经经过了岁月的沉淀，多学学它们的思想和思路。</strong></p>
<p><strong>要开始投简历了，笔试还是很重要，要不然连面试机会都没有。</strong></p>
<h2 id="参考"><a href="#参考" class="headerlink" title="参考"></a>参考</h2><p><strong>1.<a href="https://mp.weixin.qq.com/s/t0dsJeN397wO41pwBWPeTg" target="_blank" rel="noopener">https://mp.weixin.qq.com/s/t0dsJeN397wO41pwBWPeTg</a></strong></p>
<p><strong>2.<a href="https://mp.weixin.qq.com/s/IAZnN00i65Ad3BicZy5kzQ" target="_blank" rel="noopener">https://mp.weixin.qq.com/s/IAZnN00i65Ad3BicZy5kzQ</a></strong></p>

            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/binblog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/binblog/2020/08/02/Typora%E4%B8%ADEmoji%E9%9B%86%E5%90%88/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">Typora中Emoji指令集合</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/binblog/2020/07/13/%E5%A6%82%E4%BD%95%E6%89%93%E9%80%A0%E6%B0%B8%E4%B9%85%E5%B8%A6%E5%9F%9F%E5%90%8D%E4%B8%AA%E4%BA%BA%E4%B8%93%E5%B1%9E%E5%8D%9A%E5%AE%A2/">
                        <span class="hidden-mobile">如何打造带域名的永久个人专属博客</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
              <!-- Comments -->
              <div class="comments" id="comments">
                
                
  <div id="vcomments"></div>
  <script defer src="https://cdn.staticfile.org/valine/1.4.14/Valine.min.js" ></script>

  <script type="text/javascript">
    var oldLoadVa = window.onload;
    window.onload = function () {
      oldLoadVa && oldLoadVa();

      new Valine({
        el: "#vcomments",
        app_id: "vsanVmkaurLHyq2Xey9odo5V-gzGzoHsz",
        app_key: "v2hMMe4Mzz3mqpy9jwd7qx8B",
        placeholder: "说点什么吧！",
        path: window.location.pathname,
        avatar: "retro",
        meta: ["nick","mail","link"],
        pageSize: "10",
        lang: "zh-CN",
        highlight: true,
        recordIP: false,
        serverURLs: "",
      });
    };
  </script>
  <noscript>Please enable JavaScript to view the <a href="https://valine.js.org" target="_blank" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>


              </div>
            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- LeanCloud 统计PV -->
        <span id="leancloud-site-pv-container" style="display: none">
            总访问量 
            <span id="leancloud-site-pv"></span>
             次
          </span>
      
      
        <!-- LeanCloud 统计UV -->
        <span id="leancloud-site-uv-container" style="display: none">
            总访客数 
            <span id="leancloud-site-uv"></span>
             人
          </span>
      

    
  </div>


    
  <!-- 备案信息 -->
  <div class="beian">
    <a href="http://beian.miit.gov.cn/" target="_blank"
       rel="nofollow noopener">京ICP证123456号</a>
    
      <a
        href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=12345678"
        rel="nofollow noopener"
        class="beian-police"
        target="_blank"
      >
        <span class="beian-police-sep">&nbsp;|&nbsp;</span>
        
          <img src="/binblog/img/police_beian.png" srcset="/binblog/img/loading.gif" alt="police-icon" />
        
        <span>京公网安备12345678号</span>
      </a>
     
  </div>


    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/binblog/js/debouncer.js" ></script>
<script  src="/binblog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/binblog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/binblog/js/clipboard-use.js" ></script>



  <script defer>
  (function () {
    // 查询存储的记录
    function getRecord(Counter, target) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({target})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {target, time: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    }

    // 发起自增请求
    function increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    }

    // 构建自增请求体
    function buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "time": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    }

    // 校验是否为有效的 UV
    function validUV() {
      var key = 'LeanCloud_UV_Flag';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    }

    function addCount(Counter) {
      var enableIncr = 'true' === 'true' && window.location.hostname !== 'localhost';
      var getterArr = [];
      var incrArr = [];

      // 请求 PV 并自增
      var pvCtn = document.querySelector('#leancloud-site-pv-container');
      if (pvCtn || enableIncr) {
        var pvGetter = getRecord(Counter, 'site-pv').then((record) => {
          incrArr.push(buildIncrement(record.objectId))
          var ele = document.querySelector('#leancloud-site-pv');
          if (ele) {
            ele.innerText = record.time + 1;
            if (pvCtn) {
              pvCtn.style.display = 'inline';
            }
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#leancloud-site-uv-container');
      if (uvCtn || enableIncr) {
        var uvGetter = getRecord(Counter, 'site-uv').then((record) => {
          var vuv = validUV();
          vuv && incrArr.push(buildIncrement(record.objectId))
          var ele = document.querySelector('#leancloud-site-uv');
          if (ele) {
            ele.innerText = record.time + (vuv ? 1 : 0);
            if (uvCtn) {
              uvCtn.style.display = 'inline';
            }
          }
        });
        getterArr.push(uvGetter);
      }

      // 如果是文章，请求文章的浏览数，并自增
      if ('true' === 'true') {
        var viewCtn = document.querySelector('#leancloud-post-views-container');
        if (viewCtn || enableIncr) {
          var target = decodeURI('/binblog/2020/07/16/%E5%B8%B8%E7%94%A8%E7%AE%97%E6%B3%95%E4%B9%8B%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%92%8C%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95/');
          var viewGetter = getRecord(Counter, target).then((record) => {
            incrArr.push(buildIncrement(record.objectId))
            if (viewCtn) {
              var ele = document.querySelector('#leancloud-post-views');
              if (ele) {
                ele.innerText = (record.time || 0) + 1;
                viewCtn.style.display = 'inline';
              }
            }
          });
          getterArr.push(viewGetter);
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && increment(Counter, incrArr);
        })
      }
    }

    var app_id = 'vsanVmkaurLHyq2Xey9odo5V-gzGzoHsz'
    var app_key = 'v2hMMe4Mzz3mqpy9jwd7qx8B'
    var server_url = ''

    function fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': app_id,
            'X-LC-Key': app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };

      addCount(Counter);
    }

    var api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${ app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(resp => resp.json())
        .then(({api_server}) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>






  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "常用算法之排序算法和查找算法&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/binblog/js/local-search.js" ></script>
  <script>
    var path = "/binblog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  













  

  

  

  

  

  





<script src="/binblog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"model":{"jsonPath":"/binblog/live2dw/assets/koharu.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":true},"log":false,"pluginJsPath":"lib/","pluginModelPath":"assets/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>
